
package main.new_2024.month_02;


import main.dataStruct.TreeNode;

import java.util.*;

/**
 * @Description: todo 429. N 叉树的层序遍历
 * 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
 * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
 * todo 103. 二叉树的锯齿形层序遍历
 * 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 * todo 107. 二叉树的层序遍历 II
 * 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2024/2/27
 * @Param:
 * @return:
 **/
public class Solution0228 {

    //二叉树的层序遍历 II
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null){
            queue.add(root);
            while (!queue.isEmpty()){
                int size = queue.size();
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    TreeNode poll = queue.poll();
                    if (poll != null){
                        list.add(poll.val);
                        queue.add(poll.left);
                        queue.add(poll.right);
                    }
                }
                if (list.size() >0){
                    result.add(0,list);
                }
            }
        }else {
            return new ArrayList<>();
        }
        return result;
    }

    //二叉树的锯齿形层序遍历:用 自增数 判断往左还是往右
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        int temp = 0;
        if (root != null){
            queue.add(root);
            while (!queue.isEmpty()){
                int size = queue.size();
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    TreeNode poll = queue.poll();
                    if (poll != null){
                        if (temp %2 == 0){
                            list.add(poll.val);
                        }else {
                            list.add(0,poll.val);
                        }
                        queue.add(poll.left);
                        queue.add(poll.right);
                    }
                }
                if (list.size() >0)
                result.add(list);
                temp++;
            }
        }else {
            return new ArrayList<>();
        }
        return result;
    }

    //N 叉树的层序遍历
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        if (root != null){
            queue.add(root);
            while (!queue.isEmpty()){
                int size = queue.size();
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    Node poll = queue.poll();
                    if (poll != null){
                        list.add(poll.val);
                        List<Node> children = poll.children;
                        if (children != null && children.size() >0){
                            queue.addAll(children);
                        }
                    }
                }
                result.add(list);
            }
        }else {
            return new ArrayList<>();
        }

        return result;
    }

    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };

    public static void main(String[] args) {
        TreeNode one = new TreeNode(1);
        TreeNode two = new TreeNode(4);
        TreeNode t = new TreeNode(2,one,two);
        TreeNode q = new TreeNode(14);
        TreeNode w = new TreeNode(15,q,null);
        TreeNode e = new TreeNode(9);
        TreeNode r = new TreeNode(13,e,w);
        TreeNode root = new TreeNode(6,t,r);
        Solution0228 test = new Solution0228();
        List<Integer> queries = Arrays.asList(2,5,16);
    }

}

